11460. K-th Gutab

At ADA University, there are n types of gutabs available for sale. A gutab of type i costs a_i qəpiks.

Gutab is an Azerbaijani dish made from thinly rolled dough, quickly cooked on a convex griddle known as a saj. There are many variations of gutab: typically, the filling consists of pumpkin and herbs. Other regional types include Shamakhi gutab, yashyl gutab, karyn gutab, guzu gutab (with lamb), and deve gutab – traditional varieties commonly found in the village of Jorat and other regions of Azerbaijan.

Huseyn intends to buy at least one gutab. He is allowed to purchase multiple gutabs of the same type.

Find the k-th smallest possible price Huseyn may pay. If there are several combinations of gutabs that result in the same total price, that price is counted only once.

Input. The first line contains two integers: n (1 ≤ n ≤ 10) and k (1 ≤ k ≤ 2 ⋅ 10⁵).

The second line contains n integers – the prices of the different types of gutabs: a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁹).

Output. Print the k-th smallest price Huseyn can pay.

Example. The six smallest prices Huseyn can pay:

· 5 qəpik

· 10 qəpik

· 11 qəpik

· 15 qəpik

· 11 + 5 = 16 qəpik

· 20 qəpik

Thus, the answer is 20.

Sample input	Sample output
5 6 5 10 11 15 20	20

SOLUTION

data structures – set

Algorithm analysis

Add the number 0 to the set. Then perform k steps:

· Find the smallest element x in the set and remove it.

· For each i from 1 to n, add the element x + a_i to the set.

After performing k steps, the smallest element in the set will be equal to the k-th smallest price Huseyn can pay.

Algorithm implementation

Read the input data.

scanf("%d %d", &n, &k);

for (i = 0; i < n; i++)

scanf("%d", &m[i]);

Add the number 0 to the set s.

s.insert(0);

Perform k iterations.

for (i = 0; i < k; i++)

{

Find and remove the smallest element x from the set.

x = *s.begin(); s.erase(x);

For each i from 1 to n, add the element x + a_i to the set.

for (j = 0; j < n; j++)

s.insert(x + m[j]);

}

Print the answer: the k-th smallest price, which is equal to the smallest element in the set.

printf("%lld\n", *s.begin());

Python implementation – TLE

The min() function works in O(n) time because it goes through all the elements in the set to find the smallest one.

In Python, sets are unordered collections, so min() cannot take advantage of any internal ordering or structure. Instead, it checks each element individually to determine the minimum, which results in linear time complexity proportional to the number of elements in the set.

n, k = map(int, input().split())

m = list(map(int, input().split()))

s = set({0})

for _ in range(k):

x = min(s)

s.remove(x)

for value in m:

s.add(x + value)

print(min(s))

Python implementation

SortedSet maintains its elements in sorted order using an internal sorted list.
Accessing an element by index (for example, s[0] for the smallest element) is done in constant time, since SortedSet directly retrieves the element at the given index without any additional computations.

The add() operation in SortedSet from the sortedcontainers library runs in O(log n) time, where n is the number of elements in the set.

from sortedcontainers import SortedSet

n, k = map(int, input().split())

m = list(map(int, input().split()))

s = SortedSet([0])

for _ in range(k):

x = s[0]

s.discard(x)

for value in m:

s.add(x + value)

print(s[0])